SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>BHT algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">BHT algorithm</span></span>

</h1>

</header>

<p>In <a href="Quantum_computing" title="Quantum computing">quantum computing</a>, the <b>Brassard–Høyer–Tapp algorithm</b> or <b>BHT algorithm</b> is a <a href="Quantum_algorithm" title="Quantum algorithm">quantum algorithm</a> that solves the <a href="Collision_problem" title="Collision problem">collision problem</a>. In this problem, one is given <i>n</i> and an <i>r</i>-to-1 function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}</annotation>

</semantics>

</math></span><img src="./9b66cec47d8d7846d95fd8462c43ca4d44c7301b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.338ex; height:2.843ex;" alt="{\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}" loading="lazy"></span> and needs to find two inputs that <i>f</i> maps to the same output. The BHT algorithm only makes <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{1/3})}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{1/3})}</annotation>

</semantics>

</math></span><img src="./6a88ff00a145ce1c2de26b2393aa427da5180242.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.676ex; height:3.343ex;" alt="{\displaystyle O(n^{1/3})}" loading="lazy"></span> queries to <i>f</i>, which matches the lower bound of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n^{1/3})}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n^{1/3})}</annotation>

</semantics>

</math></span><img src="./e637a3eecd31200924fdb721057ca9cddb22e418.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.58ex; height:3.343ex;" alt="{\displaystyle \Omega (n^{1/3})}" loading="lazy"></span> in the <a href="Black_box" title="Black box">black box</a> model.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>The algorithm was discovered by <a href="Gilles_Brassard" title="Gilles Brassard">Gilles Brassard</a>, Peter Høyer, and Alain Tapp in 1997.<sup id="cite_ref-:0_3-0" class="reference"><a href="#cite_note-:0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> It uses <a href="Grover's_algorithm" title="Grover's algorithm">Grover's algorithm</a>, which was discovered the year before.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<p>Intuitively, the algorithm combines the square root speedup from the <a href="Birthday_attack" title="Birthday attack">birthday paradox</a> using (classical) randomness with the square root speedup from Grover's (quantum) algorithm.

</p><p>First, <i>n</i><sup>1/3</sup> inputs to <i>f</i> are selected at random and <i>f</i> is queried at all of them. If there is a collision among these inputs, then we return the colliding pair of inputs. Otherwise, all these inputs map to distinct values by <i>f</i>. Then Grover's algorithm is used to find a new input to <i>f</i> that collides. Since there are <i>n</i> inputs to <i>f</i> and <i>n</i><sup>1/3</sup> of these could form a collision with the already queried values, Grover's algorithm can find a collision with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})}">

<mrow>

<msqrt>

<mfrac>

<msup>

</mrow>

</mrow>

</msup>

</mfrac>

</msqrt>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})}</annotation>

</semantics>

</math></span><img src="./a75a50576d0ba4dc2025938b2be9860afd1c7ec4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:23.868ex; height:7.509ex;" alt="{\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})}" loading="lazy"></span> extra queries to <i>f</i>.<sup id="cite_ref-:0_3-1" class="reference"><a href="#cite_note-:0-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Element_distinctness_problem" title="Element distinctness problem">Element distinctness problem</a></li>

<li><a href="Grover's_algorithm" title="Grover's algorithm">Grover's algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAmbainis2005" class="citation journal cs1">Ambainis, A. (2005). <a rel="nofollow" class="external text" href="http://www.theoryofcomputing.org/articles/v001a003/v001a003.pdf">"Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range"</a> <span class="cs1-format">(PDF)</span>. <i><a href="Theory_of_Computing" title="Theory of Computing">Theory of Computing</a></i>. <b>1</b> (1): <span class="nowrap">37–</span>46. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4086%2Ftoc.2005.v001a003">10.4086/toc.2005.v001a003</a></span>.</cite></span>

</li>

<cite id="CITEREFKutin2005" class="citation journal cs1">Kutin, S. (2005). <a rel="nofollow" class="external text" href="https://doi.org/10.4086%2Ftoc.2005.v001a002">"Quantum Lower Bound for the Collision Problem with Small Range"</a>. <i><a href="Theory_of_Computing" title="Theory of Computing">Theory of Computing</a></i>. <b>1</b> (1): <span class="nowrap">29–</span>36. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4086%2Ftoc.2005.v001a002">10.4086/toc.2005.v001a002</a></span>.</cite></span>

</li>

<li id="cite_note-:0-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFBrassardHøyerTapp1998" class="citation cs2">Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998), "Quantum Algorithm for the Collision Problem", in Lucchesi, Claudio L.; Moura, Arnaldo V. (eds.), <i>LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings</i>, Lecture Notes in Computer Science, vol. 1380, Springer, pp. <span class="nowrap">163–</span>169, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9705002">quant-ph/9705002</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0054319">10.1007/BFb0054319</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3116149">3116149</a></cite></span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Quantum_information_science667" style="padding:3px"><table class="nowraplinks hlist mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Quantum_information_science667" style="font-size:114%;margin:0 4em"><a href="Quantum_information_science" title="Quantum information science">Quantum information science</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="DiVincenzo's_criteria" title="DiVincenzo's criteria">DiVincenzo's criteria</a></li>

<li><a href="Quantum_computing" title="Quantum computing">Quantum computing</a>

<ul><li><a href="Timeline_of_quantum_computing_and_communication" title="Timeline of quantum computing and communication">timeline</a></li></ul></li>

<li><a href="Quantum_information" title="Quantum information">Quantum information</a></li>

<li><a href="Quantum_programming" title="Quantum programming">Quantum programming</a></li>

<li><a href="Quantum_simulator" title="Quantum simulator">Quantum simulation</a></li>

<li><a href="Qubit" title="Qubit">Qubit</a>

<ul><li><a href="Physical_and_logical_qubits" title="Physical and logical qubits">physical vs. logical</a></li></ul></li>

<li><a href="List_of_quantum_processors" title="List of quantum processors">Quantum processors</a>

<ul><li><a href="Cloud-based_quantum_computing" title="Cloud-based quantum computing">cloud-based</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Eastin%E2%80%93Knill_theorem" title="Eastin–Knill theorem">Eastin–Knill</a></li>

<li><a href="Gleason's_theorem" title="Gleason's theorem">Gleason's</a></li>

<li><a href="Gottesman%E2%80%93Knill_theorem" title="Gottesman–Knill theorem">Gottesman–Knill</a></li>

<li><a href="Holevo's_theorem" title="Holevo's theorem">Holevo's</a></li>

<li><a href="No-broadcasting_theorem" title="No-broadcasting theorem">No-broadcasting</a></li>

<li><a href="No-cloning_theorem" title="No-cloning theorem">No-cloning</a></li>

<li><a href="No-communication_theorem" title="No-communication theorem">No-communication</a></li>

<li><a href="No-deleting_theorem" title="No-deleting theorem">No-deleting</a></li>

<li><a href="No-hiding_theorem" title="No-hiding theorem">No-hiding</a></li>

<li><a href="No-teleportation_theorem" title="No-teleportation theorem">No-teleportation</a></li>

<li><a href="Quantum_speed_limit_theorems" class="mw-redirect" title="Quantum speed limit theorems">Quantum speed limit</a></li>

<li><a href="Threshold_theorem" title="Threshold theorem">Threshold</a></li>

<li><a href="Solovay%E2%80%93Kitaev_theorem" title="Solovay–Kitaev theorem">Solovay–Kitaev</a></li>

<li><a href="Schr%C3%B6dinger%E2%80%93HJW_theorem" class="mw-redirect" title="Schrödinger–HJW theorem">Schrödinger-HJW</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum<br>communication</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_capacity" title="Classical capacity">Classical capacity</a>

<ul><li><a href="Entanglement-assisted_classical_capacity" title="Entanglement-assisted classical capacity">entanglement-assisted</a></li>

<li><a href="Quantum_capacity" title="Quantum capacity">quantum capacity</a></li></ul></li>

<li><a href="Entanglement_distillation" title="Entanglement distillation">Entanglement distillation</a></li>

<li><a href="Entanglement_swapping" title="Entanglement swapping">Entanglement swapping</a></li>

<li><a href="Monogamy_of_entanglement" title="Monogamy of entanglement">Monogamy of entanglement</a></li>

<li><a href="Quantum_channel" title="Quantum channel">Quantum channel</a>

<ul><li><a href="Quantum_network" title="Quantum network">quantum network</a></li></ul></li>

<li><a href="Quantum_state_purification" title="Quantum state purification">State purification</a></li>

<li><a href="Quantum_teleportation" title="Quantum teleportation">Quantum teleportation</a>

<ul><li><a href="Quantum_energy_teleportation" title="Quantum energy teleportation">quantum energy teleportation</a></li>

<li><a href="Quantum_gate_teleportation" title="Quantum gate teleportation">quantum gate teleportation</a></li></ul></li>

<li><a href="Superdense_coding" title="Superdense coding">Superdense coding</a></li></ul>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Quantum_cryptography24" scope="row" class="navbox-group" style="width:1%"><a href="Quantum_cryptography" title="Quantum cryptography">Quantum cryptography</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Post-quantum_cryptography" title="Post-quantum cryptography">Post-quantum cryptography</a></li>

<li><a href="Quantum_coin_flipping" title="Quantum coin flipping">Quantum coin flipping</a></li>

<li><a href="Quantum_money" title="Quantum money">Quantum money</a></li>

<li><a href="Quantum_key_distribution" title="Quantum key distribution">Quantum key distribution</a>

<li><a href="List_of_quantum_key_distribution_protocols" title="List of quantum key distribution protocols">other protocols</a></li></ul></li>

<li><a href="Quantum_secret_sharing" title="Quantum secret sharing">Quantum secret sharing</a></li></ul>

</div></td></tr></tbody></table><div>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_algorithm" title="Quantum algorithm">Quantum algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Algorithmic_cooling" title="Algorithmic cooling">Algorithmic cooling</a></li>

<li><a href="Amplitude_amplification" title="Amplitude amplification">Amplitude amplification</a></li>

<li><a href="Bernstein%E2%80%93Vazirani_algorithm" title="Bernstein–Vazirani algorithm">Bernstein–Vazirani</a></li>

<li><a href="Boson_sampling" title="Boson sampling">Boson sampling</a></li>

<li><a href="Deutsch%E2%80%93Jozsa_algorithm" title="Deutsch–Jozsa algorithm">Deutsch–Jozsa</a></li>

<li><a href="Grover's_algorithm" title="Grover's algorithm">Grover's</a></li>

<li><a href="Hidden_subgroup_problem" title="Hidden subgroup problem">Hidden subgroup</a></li>

<li><a href="Magic_state_distillation" title="Magic state distillation">Magic state distillation</a></li>

<li><a href="Quantum_annealing" title="Quantum annealing">Quantum annealing</a></li>

<li><a href="Quantum_counting_algorithm" title="Quantum counting algorithm">Quantum counting</a></li>

<li><a href="Quantum_Fourier_transform" title="Quantum Fourier transform">Quantum Fourier transform</a></li>

<li><a href="Quantum_optimization_algorithms" title="Quantum optimization algorithms">Quantum optimization</a></li>

<li><a href="Quantum_phase_estimation_algorithm" title="Quantum phase estimation algorithm">Quantum phase estimation</a></li>

<li><a href="Simon's_problem" title="Simon's problem">Simon's</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_complexity_theory" title="Quantum complexity theory">Quantum<br>complexity theory</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="PostBQP" title="PostBQP">PostBQP</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum <br> processor benchmarks</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Quantum_supremacy" title="Quantum supremacy">Quantum supremacy</a></li>

<li><a href="Quantum_volume" title="Quantum volume">Quantum volume</a></li>

<li><a href="Randomized_benchmarking" title="Randomized benchmarking">Randomized benchmarking</a>

<li><a href="Relaxation_(NMR)" title="Relaxation (NMR)">Relaxation times</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum<br><a href="Model_of_computation" title="Model of computation">computing models</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adiabatic_quantum_computation" title="Adiabatic quantum computation">Adiabatic quantum computation</a></li>

<li><a href="Continuous-variable_quantum_information" title="Continuous-variable quantum information">Continuous-variable quantum information</a></li>

<li><a href="One-way_quantum_computer" title="One-way quantum computer">One-way quantum computer</a>

<ul><li><a href="Cluster_state" title="Cluster state">cluster state</a></li></ul></li>

<li><a href="Quantum_circuit" title="Quantum circuit">Quantum circuit</a>

<ul><li><a href="Quantum_logic_gate" title="Quantum logic gate">quantum logic gate</a></li></ul></li>

<li><a href="Quantum_machine_learning" title="Quantum machine learning">Quantum machine learning</a>

<ul><li><a href="Quantum_neural_network" title="Quantum neural network">quantum neural network</a></li></ul></li>

<li><a href="Quantum_Turing_machine" title="Quantum Turing machine">Quantum Turing machine</a></li>

<li><a href="Topological_quantum_computer" title="Topological quantum computer">Topological quantum computer</a></li>

<li><a href="Hamiltonian_quantum_computation" title="Hamiltonian quantum computation">Hamiltonian quantum computation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_error_correction" title="Quantum error correction">Quantum<br>error correction</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Codes

<ul><li><a href="Five-qubit_error_correcting_code" title="Five-qubit error correcting code">5 qubit</a></li>

<li><a href="Quantum_convolutional_code" title="Quantum convolutional code">quantum convolutional</a></li>

<li><a href="Stabilizer_code" title="Stabilizer code">stabilizer</a></li>

<li><a href="Bacon%E2%80%93Shor_code" title="Bacon–Shor code">Bacon–Shor</a></li>

<li><a href="Steane_code" title="Steane code">Steane</a></li>

<li><a href="Toric_code" title="Toric code">Toric</a></li>

<li><a href="Entanglement-assisted_stabilizer_formalism" title="Entanglement-assisted stabilizer formalism">Entanglement-assisted</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Physical<br>implementations</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_optics" title="Quantum optics">Quantum optics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cavity_quantum_electrodynamics" title="Cavity quantum electrodynamics">Cavity QED</a></li>

<li><a href="Circuit_quantum_electrodynamics" title="Circuit quantum electrodynamics">Circuit QED</a></li>

<li><a href="Linear_optical_quantum_computing" title="Linear optical quantum computing">Linear optical QC</a></li>

<li><a href="KLM_protocol" title="KLM protocol">KLM protocol</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Ultracold_atom" title="Ultracold atom">Ultracold atoms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Neutral_atom_quantum_computer" title="Neutral atom quantum computer">Neutral atom QC</a></li>

<li><a href="Trapped-ion_quantum_computer" title="Trapped-ion quantum computer">Trapped-ion QC</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Spin_(physics)" title="Spin (physics)">Spin</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Spin_qubit_quantum_computer" title="Spin qubit quantum computer">Spin qubit QC</a></li>

<li><a href="Nitrogen-vacancy_center" title="Nitrogen-vacancy center">NV center</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Superconducting_quantum_computing" title="Superconducting quantum computing">Superconducting</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Charge_qubit" title="Charge qubit">Charge qubit</a></li>

<li><a href="Flux_qubit" title="Flux qubit">Flux qubit</a></li>

<li><a href="Phase_qubit" title="Phase qubit">Phase qubit</a></li>

<li><a href="Transmon" title="Transmon">Transmon</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_programming" title="Quantum programming">Quantum<br>programming</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="OpenQASM" title="OpenQASM">OpenQASM</a>–<a href="Qiskit" title="Qiskit">Qiskit</a>–<a href="IBM_Quantum_Experience" class="mw-redirect" title="IBM Quantum Experience">IBM QX</a></li>

<li><a href="Quil_(instruction_set_architecture)" title="Quil (instruction set architecture)">Quil</a>–<a href="Rigetti_Computing" title="Rigetti Computing">Forest/Rigetti QCS</a></li>

<li><a href="Libquantum" title="Libquantum">libquantum</a></li>

<li><a href="Quantum_programming" title="Quantum programming">many others...</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Quantum information science</li>

<li><span class="noviewer" typeof="mw:File"><span title="Template"></span></span> Quantum mechanics topics</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-08" href="https://en.wikipedia.org/wiki/?title=BHT_algorithm&oldid=1279378972">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>